//#include<iostream>
//using namespace std;
//
//struct Node {
//	Node(int v) : _val(v), _left(nullptr), _right(nullptr) 
//	{}
//
//	int _val;
//	Node* _left;
//	Node* _right;
//};
//
//class BST {
//public:
//	bool insert(int v) {
//		if (_p == nullptr) {
//			_p = new Node(v);
//			return true;
//		}
//
//		Node* cur = _p;
//		while (cur) {
//			if (v == cur->_val) {
//				return false;
//			}
//			if (v > cur->_val) {
//				if (cur->_right) cur = cur->_right;
//				else break;
//			}
//			else {
//				if (cur->_left) cur = cur->_left;
//				else break;
//			}
//		}
//		if (v > cur->_val) cur->_right = new Node(v); 
//		else cur->_left = new Node(v);
//		return true;
//	}
//	Node* get() { return _p; }
//
//private:
//	Node* _p = nullptr;
//};
//
//Node* insert(Node* root, int val) {
//	if (root == nullptr) {
//		return new Node(val);
//	}
//
//	if (val < root->_val) {
//		root->_left = insert(root->_left, val);
//	}
//
//	if (val > root->_val) {
//		root->_right = insert(root->_right, val);
//	}
//	
//	return root;
//}
//
//void inOrder(Node* root) {
//	if (root == nullptr) return;
//	inOrder(root->_left);
//	cout << root->_val << " ";
//	inOrder(root->_right);
//}
//
//int main()
//{
//	int arr[] = { 1, 5, 2, 2, 3, 9 };
//	BST t;
//	for (int i = 0; i < sizeof(arr) / sizeof(int); ++i) {
//		t.insert(arr[i]);
//	}
//	inOrder(t.get());
//	cout << endl;
//
//	Node* root = nullptr;
//	for (int i = 0; i < sizeof(arr) / sizeof(int); ++i) {
//		root = insert(root, arr[i]);
//	}
//	inOrder(root);
//	cout << endl;
//
//	
//	return 0;
//}